package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-19
 * Description
 */
public class Solution60 {

    /**
     * 方法一，失败，在m=1时，无法输出正确的结果内容
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) {
            return head;
        }
        ListNode current = head, preNode = null, preStand = null, lastStand = null;
        while (m > 2 && current != null) {
            current = current.next;
            m--;
        }
        preStand = current;
        lastStand = current.next;
        current = current.next;
        int distance = n - m + 1;
        while (distance > 0 && current != null) {
            ListNode temp = current.next;
            current.next = preNode;
            preNode = current;
            current = temp;
            distance--;
        }
        preStand.next = preNode;
        lastStand.next = current;
        return head;
    }

    /**
     * 方法二，使用一个哑结点，来实现这个功能
     * @param head
     * @param m
     * @param n
     * @return
     */
    public ListNode reverseBetween2(ListNode head, int m, int n) {
        ListNode dummpy = new ListNode(0);
        dummpy.next = head;
        ListNode current = dummpy;
        //找到翻转的前一个节点的内容
        for (int i = 1; i < m; i++) {
            current = current.next;
        }
        ListNode preStand = current, lastStand = current.next, preNode = null;
        current = current.next;
        int distance = n - m + 1;
        while (distance > 0 && current != null) {
            ListNode temp = current.next;
            current.next = preNode;
            preNode = current;
            current = temp;
            distance--;
        }

        preStand.next = preNode;
        lastStand.next = current;
        return dummpy.next;

    }

    public static void main(String[] args) {
        Solution60 solution60 = new Solution60();
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        ListNode listNode = solution60.reverseBetween(node1, 2, 4);

    }
}

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}
